<!DOCTYPE html>
<html>
    <head>
        <meta charset="utf-8">
        <meta name="viewport" content="width=device-width,initial-scale=1.0">
        <meta http-equiv="X-UA-Compatible" content="ie=edge,chrome=1">
        <title>75.颜色分类</title>
    </head>
    <body>
        <section>
            给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

            此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

        </section>
        <h1>方法一(三路快排)</h1>
        <pre class="language-JavaScript">
            <code>
                var sortColors = function(nums) {
                    let l = 0, r = nums.length - 1;// [0, l)是0，[l, r]是1, (r, nums.length - 1]是2
    
                    let k = 0;
                    while(k >= l && k <= r) {
                        if(nums[k] === 0) {
                            nums[k] = 1;
                            nums[l ++] = 0;
                        } else if(nums[k] === 2) {
                            nums[k] = nums[r];
                            nums[r --] = 2;
                            k --;
                        }
                        k ++;
                    }
                    return nums;
                };
            </code>
        </pre>
        <h1>方法二（快速排序）</h1>
        <pre class="language-JavaScript">
            <code>
                var sortColors = function(nums) {
                    quickSort(nums, 0, nums.length - 1);
                    return nums;
                }
                function quickSort(arr, left, right) {
                    if(left >= right) {
                        return;
                    }
                    let privot = findPrivot(arr, left, right);
                    // [left, l) 是小于privot
                    // [l, k)是等于privot
                    // (r, right]是大于provit
                    let l = left, k = left, r = right;
                    while(k >= l && k <= r) {
                        if(arr[k] === privot) {
                            k ++;
                        } else if(arr[k] < privot) {
                            swap(arr, l, k);
                            l ++;
                            k ++;
                        } else {
                            swap(arr, k, r);
                            r--;
                        }
                    }
                    quickSort(arr, left, l - 1);
                    quickSort(arr, r + 1, right);
                    
                }
    
                function swap(arr, i, j) {
                    let temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
    
                function findPrivot(arr, left, right) {
                    let privot = arr[left];
                    if(left + 2 <= right) {
                    if( (arr[left + 1] - privot) * (arr[left + 1] - arr[left + 2]) < 0) {
                        privot = arr[left + 1];
                    }
                    else if( (arr[left + 2] - privot) * (arr[left + 2] - arr[left + 1]) < 0) {
                        privot = arr[left + 2];
                    }
                    }
                    return privot;
                }
            </code>
        </pre>
        <script>
            var sortColors = function(nums) {
                let l = 0, r = nums.length - 1;// [0, l)是0，[l, r]是1, (r, nums.length - 1]是2

                let k = 0;
                while(k >= l && k <= r) {//[l, ..., k)为1
                    if(nums[k] === 0) {
                        nums[k] = 1;
                        nums[l ++] = 0;
                    } else if(nums[k] === 2) {
                        nums[k] = nums[r];
                        nums[r --] = 2;
                        k --;
                    }
                    k ++;
                }
                return nums;
            };
            var sortColors = function(nums) {
                quickSort(nums, 0, nums.length - 1);
                return nums;
            }
            function quickSort(arr, left, right) {
                if(left >= right) {
                    return;
                }
                let privot = findPrivot(arr, left, right);
                // [left, l) 是小于privot
                // [l, k)是等于privot
                // (r, right]是大于provit
                let l = left, k = left, r = right;
                while(k >= l && k <= r) {
                    if(arr[k] === privot) {
                        k ++;
                    } else if(arr[k] < privot) {
                        swap(arr, l, k);
                        l ++;
                        k ++;
                    } else {
                        swap(arr, k, r);
                        r--;
                    }
                }
                quickSort(arr, left, l - 1);
                quickSort(arr, r + 1, right);
                
            }

            function swap(arr, i, j) {
                let temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }

            function findPrivot(arr, left, right) {
                let privot = arr[left];
                if(left + 2 <= right) {
                if( (arr[left + 1] - privot) * (arr[left + 1] - arr[left + 2]) < 0) {
                    privot = arr[left + 1];
                }
                else if( (arr[left + 2] - privot) * (arr[left + 2] - arr[left + 1]) < 0) {
                    privot = arr[left + 2];
                }
                }
                return privot;
            }

            
            console.log(sortColors([2,0,2,1,1,0]))
        </script>
    </body>
</html>